package chapter16;

import java.util.ArrayList;
import java.util.List;

/**
 * 贪心-活动选择(选择出最大兼容活动集合)
 * <p>
 * 前置条件：按结束时间单调递增
 * <p>
 * 最优子结构：s开始时间,f结束时间
 * max(s[i],f[j])
 * 因为结束时间按从小到大排序,从第一个开始,找到开始时间大于前一个活动的结束时间的活动
 */
public class ActivitySelector {

    public static void recursiveActivitySelector(int[] s, int[] f, int k, int n, List<Integer> r) {
        int m = k + 1;
        if (k == 0) {
            r.add(1);
        }
        while (m <= n && s[m] < f[k]) {
            m++;
        }
        if (m <= n) {
            r.add(m + 1);
            recursiveActivitySelector(s, f, m, n, r);
        }
    }


    public static List<Integer> greedyActivitySelector(int[] s, int[] f) {
        int k = 1;
        List<Integer> r = new ArrayList<>();
        r.add(1);
        for (int i = 1; i < s.length; i++) {
            if (s[i] >= f[k]) {
                r.add(i + 1);
                k = i;
            }
        }
        return r;
    }

    public static List<Integer> greedyActivitySelector2(int[] s, int[] f) {
        int k = s.length - 1;
        List<Integer> r = new ArrayList<>();
        for (int i = s.length - 2; i >= 0; i--) {
            if (s[k] > f[i]) {
                r.add(k + 1);
                k = i;
            }
        }
        r.add(1);
        return r;
    }

}
